Papers with search algorithm
Diving into the Decoding Space of Non-Autoregressive Models via Lexically Constrained Search (2026.acl-short)
Copied to clipboard
| Challenge: | Non-autoregressive (NAR) models have been mainly developed to improve decoding efficiency. |
| Approach: | They propose a search-based decoding algorithm which is comparable to the autoregressive Grid Beam Search (GBS) method. |
| Outcome: | The proposed method does not suffer from the MAP degradation issue as the autoregressive method does. |
Language Models are Crossword Solvers (2025.naacl-long)
Copied to clipboard
| Challenge: | Modern crossword models demonstrate astounding skills in reasoning, coding, wordplay, question answering, and a multitude of other tasks. |
| Approach: | They propose a search algorithm that generalizes well and can support answers with sound rationale by solving full crossword grids with out-of-the-box LLMs. |
| Outcome: | The proposed model outperforms state-of-the-art models in solving crossword grids for the first time and generalizes well. |
Searching for Better Database Queries in the Outputs of Semantic Parsers (2023.findings-eacl)
Copied to clipboard
| Challenge: | generating a database query from a question in natural language is a longstanding task . the task is amplified when the system needs to generalize to databases unseen at training. |
| Approach: | They propose to generalize a query to databases unseen at training . they use state-of-the-art semantic parsers to find queries that meet the criterion . |
| Outcome: | The proposed approach finds that many queries pass all tests on different datasets. |
ComSearch: Equation Searching with Combinatorial Strategy for Solving Math Word Problems with Weak Supervision (2023.eacl-main)
Copied to clipboard
| Challenge: | Existing weakly-supervised methods for solving math word problems are expensive and time-consuming. |
| Approach: | They propose a weakly-supervised approach to solve math word problems . they propose 'comsearch' algorithm which compresses the search space by excluding mathematically equivalent equations. |
| Outcome: | The proposed algorithm can compress the search space by excluding mathematically equivalent equations. |
Value-based Search in Execution Space for Mapping Instructions to Programs (N19-1)
Copied to clipboard
| Challenge: | Existing methods to map instructions to programs require searching for good programs at training time. |
| Approach: | They propose a search algorithm that uses the target world state to train a critic network that predicts the expected reward of every search state. |
| Outcome: | The proposed algorithm significantly improves on all three domains compared to baselines on the SCONE dataset. |
Target Conditioning for One-to-Many Generation (2020.findings-emnlp)
Copied to clipboard
| Challenge: | Neural Machine Translation models lack diversity in their generated translations, even when paired with search algorithm, like beam search. |
| Approach: | They propose to model one-to-many mapping by conditioning a decoder on a latent variable that represents the domain of target sentences. |
| Outcome: | The proposed method can scale to any number of domains without affecting performance or training time. |
Reanalyzing the Most Probable Sentence Problem: A Case Study in Explicating the Role of Entropy in Algorithmic Complexity (2021.eacl-main)
Copied to clipboard
| Challenge: | Existing descriptive complexity measures are ineffective at describing algorithms' behaviour, and can make an apparently tractable problem seem NP-complete. |
| Approach: | They propose to use statistical measures to give an updated analysis of the complexity of the NP-complete most probable sentence problem for pCFGs. |
| Outcome: | The proposed method can be applied to word sense disambiguation and inference tasks. |
Massive-scale Decoding for Text Generation using Lattices (2022.naacl-main)
Copied to clipboard
| Challenge: | Conditional neural text generation models generate high-quality outputs, but often focus on a mode when what we really want is a diverse set of options. |
| Approach: | They propose a search algorithm to construct lattices encoding a massive number of generation options. |
| Outcome: | The proposed algorithm encodes thousands of diverse options that remain grammatical and high-quality into one lattice. |
Real-Valued Logics for Typological Universals: Framework and Application (2020.coling-main)
Copied to clipboard
| Challenge: | a framework for typological statements captures the truth value of a formula on a given data source. |
| Approach: | They propose a framework which captures the empirical truth value of a formula on a given data source. |
| Outcome: | The proposed framework can be used to express typological statements on multilingual treebanks with comparable annotation. |
A Training Data Recipe to Accelerate A* Search with Language Models (2024.findings-emnlp)
Copied to clipboard
| Challenge: | Recent studies compare Large Language Models (LLMs) to System 1 . a* and A* are heuristic search algorithms with a wall-clock speed-up of search. |
| Approach: | They propose a method to disentangle the requirements of A* from the requirements for LLMs to generalise on this task. |
| Outcome: | The proposed method reduces the number of iterations required to find the solutions by 15x and a wall-clock speed-up of search up to 5x. |
Search to Pass Messages for Temporal Knowledge Graph Completion (2022.findings-emnlp)
Copied to clipboard
| Challenge: | Recent studies on missing facts in temporal knowledge graphs are based on hand-designed architectures and fail to explore the diverse topological and temporal properties of TKGs. |
| Approach: | They propose to use neural architecture search to design a data-specific message passing architecture for TKG completion. |
| Outcome: | The proposed architectures achieve the state-of-the-art performance on three benchmark datasets. |
Explore-Instruct: Enhancing Domain-Specific Instruction Coverage through Active Exploration (2023.emnlp-main)
Copied to clipboard
| Challenge: | Existing data for instruction-tuning are inadequate for a wide range of tasks, limiting the scope for nuanced comprehension and interactions within these domains. |
| Approach: | They propose to use Large Language Models to explore a multitude of variations or possibilities to improve instruction-tuning data by active exploration. |
| Outcome: | The proposed approach improves domain-specific instruction coverage and shows significant improvements over baselines. |